package com.jia.explore.dynamicprogramming.knapsack;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @program: Leetcode
 * @description: 多重背包 https://www.acwing.com/problem/content/5/
 *  物品s 可以分为1 2 4 6 8 ... 2^(log(s) - 1) , s - 2^log(s) + 1
 *      根据01背包，取与不取，可以表示 0...s所有的情况
 *      数据范围
 *      0<N≤1000
 *      0<V≤2000
 *      0<vi,wi,si≤2000
 *      物品的个数可以有N * log(s)个，1000 * log(2000) = 11000
 *      01背包，背包大小为2000， 那么总时间复杂度为220000000 10^7
 * @author: STU756
 * @create: 2020-08-11 12:50
 */
public class Dy_MixedBackpack {
    static class Thing{
        int s;
        int v;
        int w;
        public Thing(int s, int v, int w) {
            this.s = s;
            this.v = v;
            this.w = w;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int N = 1010;
        int index = 1;
        List<Thing> things = new ArrayList<>();
        while(index <= n) {
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            int s = scanner.nextInt();
            //si=−1 表示第 i 种物品只能用1次；
            //si=0 表示第 i 种物品可以用无限次；
            //si>0 表示第 i 种物品可以使用 si 次；
            if(s < 0) {
                things.add(new Thing(-1, v, w));
            }else if(s == 0) {
                things.add(new Thing(0, v, w));
            }else {
                //多从背包进行拆分
                for(int k = 1; k <= s; k *= 2) {
                    s -= k;
                    things.add(new Thing(-1, k * v, k * w));
                }
                if(s > 0) things.add(new Thing(-1, s * v, s * w));
            }
            index++;
        }

        int[] f = new int[N];
        for(Thing t : things) {
            if(t.s < 0) {
                //01背包
                for(int j = m; j >= t.v; j--) {
                    f[j] = Math.max(f[j], f[j-t.v] + t.w);
                }
            }else if(t.s == 0) {
                //完全背包
                for(int j = t.v; j <= m; j++) {
                    f[j] = Math.max(f[j], f[j - t.v] + t.w);
                }
            }
        }
        System.out.println(f[m]);
    }
}
